﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using StudentAI.BitBoard;
using UvsChess;

namespace StudentAI.Algo
{
    internal static class Minimax
    {
        //Sort boards base on value (best first)
        private static int Sort(Board s2, Board s1)
        {
            return (s1.Score).CompareTo(s2.Score);
        }

        //Sort moves based on value (best first);
        private static int Sort(Move s2, Move s1)
        {
            return (s1.Score).CompareTo(s2.Score);
        }

        private static long timelimit = 0;

        /// <summary>
        /// Iterative calls AlphaBetaRoot with higher depth until the time runs out.
        /// </summary>
        /// <param name="beforeBoard"></param>
        /// <param name="logger"></param>
        /// <param name="timelimit"></param>
        /// <returns></returns>
        internal static Board IterativeDeepening(Board beforeBoard, IChessAI logger, long timelimit)
        {
            //Cuttoff time when we have to quit
            Minimax.timelimit = timelimit;

            //We start with two deep, iterative deepen from there
            byte depth = 2;
            byte highestdepth = 2;

            Board best = null;
            while (DateTime.Now.Ticks < timelimit && depth < 50) //iterative deepening
            {
                Board b = AlphaBetaRoot(beforeBoard, depth);
                depth++;

                //Check if we completed the whole search
                if ((best == null || DateTime.Now.Ticks < timelimit) && b.LastMove != null)
                {
                    highestdepth = (byte)(depth + 1);
                    best = b;
                }
            }
            logger.Log("Depth reached: " + highestdepth);
            return best;
        }

        /// <summary>
        /// Entry point for Negamax with alpha-beta, returns best board (which has the move that was done to get there)
        /// </summary>
        /// <param name="beforeBoard"></param>
        /// <param name="searchDepth">Depth to search</param>
        /// <returns></returns>
        internal static Board AlphaBetaRoot(Board beforeBoard, byte searchDepth)
        {
            int alpha = -400000000;
            const int beta = 400000000;
            Board bestBoard = new Board(short.MinValue);

            //We are going to store our result boards here 
            List<Board> Positions = new List<Board>(30);

            for (byte x = 0; x < 64; x++)
            {
                Piece piece = beforeBoard.Squares[x];

                //Make sure there is a piece on the square
                if (piece == null)
                {
                    continue;
                }

                //Make sure the color is the same color as the one we are moving.
                if (piece.PieceColor != beforeBoard.WhoseMove)
                    continue;

                //For each valid move for this piece
                foreach (byte dst in piece.ValidMoves)
                {
                    //We make copies of the board and move so that we can move it without effecting the parent board
                    Board board = beforeBoard.FastCopy();

                    //Make move so we can examine it
                    board.MovePiece(x, dst, ChessPieceType.Queen);

                    //We Generate Valid Moves for Board
                    PieceValidMoves.GenerateValidMoves(board);

                    //Invalid Move
                    if (board.WhiteCheck && beforeBoard.WhoseMove == ChessColor.White)
                    {
                        continue;
                    }

                    //Invalid Move
                    if (board.BlackCheck && beforeBoard.WhoseMove == ChessColor.Black)
                    {
                        continue;
                    }

                    //We calculate the board score
                    ScoreHeuristic.EvaluateBoardScore(board);

                    //Invert Score to support Negamax
                    board.Score = SideToMoveScore(board.Score, board.WhoseMove);
                    Positions.Add(board);
                }
            }

            Positions.Sort(Sort);
            //Can I make an instant mate?
            foreach (Board pos in Positions)
            {
                int value = -AlphaBeta(pos, 1, 1, -beta, -alpha, false);

                if (value >= 32767)
                {
                    return pos;
                }
            }
            int currentBoard = 0;
            alpha = -400000000;
            foreach (Board pos in Positions)
            {
                currentBoard++;
                int value = -AlphaBeta(pos, searchDepth, 1, -beta, -alpha, false);
                pos.Score = value;

                //If value is greater then alpha this is the best board
                if (value > alpha)
                {
                    alpha = value;
                    bestBoard = new Board(pos);
                }
            }
            return bestBoard;
        }

        /// <summary>
        /// Perform Negamax with alphabeta pruning, returning score of the board
        /// </summary>
        /// <param name="beforeBoard"></param>
        /// <param name="depthRemaining"></param>
        /// <param name="depth"></param>
        /// <param name="alpha"></param>
        /// <param name="beta"></param>
        /// <param name="extended"></param>
        /// <returns></returns>
        private static int AlphaBeta(Board beforeBoard, byte depthRemaining, byte depth, int alpha, int beta, bool extended)
        {
            //Try to prevent back and forth stalemate
            if (beforeBoard.RepeatedMove >= 5)
                return 0;

            //End Main Search with Quiescence
            if (depthRemaining == 0 || DateTime.Now.Ticks >= timelimit)
            {
                if (!extended && beforeBoard.BlackCheck || beforeBoard.WhiteCheck)
                {
                    depthRemaining++;
                    extended = true;
                }
                else
                {
                    //Perform a Quiessence Search
                    int score = Quiescence(beforeBoard, alpha, beta, (byte)(depth + 1));
                    return score;
                }
            }
            List<Move> positions = GetMoves(beforeBoard);

            //Special code to check for insta-mate
            if (beforeBoard.WhiteCheck || beforeBoard.BlackCheck || positions.Count == 0)
            {
                if (PieceValidMoves.SearchForMate(beforeBoard.WhoseMove, beforeBoard, ref beforeBoard.BlackMate, ref beforeBoard.WhiteMate, ref beforeBoard.StaleMate))
                {
                    if (beforeBoard.BlackMate)
                    {
                        if (beforeBoard.WhoseMove == ChessColor.Black)
                            return -32767 - depthRemaining;

                        return 32767 + depthRemaining;
                    }
                    if (beforeBoard.WhiteMate)
                    {
                        if (beforeBoard.WhoseMove == ChessColor.Black)
                            return 32767 + depthRemaining;

                        return -32767 - depthRemaining;
                    }
                    //If Not Mate then StaleMate
                    return 0;
                }
            }

            // setKillerMoves(positions, depth);
            positions.Sort(Sort);

            foreach (Move move in positions)
            {
                //Make a copy
                Board board = beforeBoard.FastCopy();

                //Move Piece
                board.MovePiece(move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves(board);

                if (board.BlackCheck && beforeBoard.WhoseMove == ChessColor.Black)
                {
                    //Invalid Move
                    continue;
                }

                if (board.WhiteCheck && beforeBoard.WhoseMove == ChessColor.White)
                {
                    //Invalid Move
                    continue;
                }

                int value = -AlphaBeta(board, (byte)(depthRemaining - 1), (byte)(depth + 1), -beta, -alpha, extended);

                if (value >= beta)
                {
                    return beta;
                }
                if (value > alpha)
                {
                    alpha = (int)value;
                }
            }
            return alpha;
        }

        /// <summary>
        /// This is exactly the same as AlphaBeta except it doesn't count down a depth (goes till "calm" board state)
        /// The movement generator, EvaluateMovesQ, only returns capture moves
        /// </summary>
        /// <param name="beforeBoard"></param>
        /// <param name="alpha"></param>
        /// <param name="beta"></param>
        /// <param name="depth"></param>
        /// <returns></returns>
        private static int Quiescence(Board beforeBoard, int alpha, int beta, byte depth)
        {
            //Evaluate Score
            ScoreHeuristic.EvaluateBoardScore(beforeBoard);
            //Invert Score to support Negamax
            beforeBoard.Score = SideToMoveScore(beforeBoard.Score, beforeBoard.WhoseMove);
            if (beforeBoard.Score >= beta)
            {
                return beta;
            }

            if (beforeBoard.Score > alpha)
                alpha = beforeBoard.Score;

            List<Move> positions = GetCaptureMoves(beforeBoard);

            if (positions.Count == 0 || DateTime.Now.Ticks >= timelimit)
            {
                return beforeBoard.Score;
            }
            positions.Sort(Sort);

            foreach (Move move in positions)
            {
                //Make a copy
                Board board = beforeBoard.FastCopy();

                //Move Piece
                board.MovePiece(move.SrcPosition, move.DstPosition, ChessPieceType.Queen);

                //We Generate Valid Moves for Board
                PieceValidMoves.GenerateValidMoves(board);

                if (board.BlackCheck)
                {
                    if (beforeBoard.WhoseMove == ChessColor.Black)
                    {
                        //Invalid Move
                        continue;
                    }
                }

                if (board.WhiteCheck)
                {
                    if (beforeBoard.WhoseMove == ChessColor.White)
                    {
                        //Invalid Move
                        continue;
                    }
                }

                int value = -Quiescence(board, -beta, -alpha, (byte)(depth + 1));

                if (value >= beta)
                {
                    return beta;
                }

                if (value > alpha)
                    alpha = value;

            }
            return alpha;
        }

        #region private helpers

        private class Move
        {
            internal byte SrcPosition;
            internal byte DstPosition;
            internal int Score;
        }

        private static List<Move> GetMoves(Board board)
        {
            //We are going to store our result boards here           
            List<Move> positions = new List<Move>();

            for (byte x = 0; x < 64; x++)
            {
                Piece piece = board.Squares[x];

                //Make sure there is a piece on the square
                if (piece == null)
                    continue;

                //Make sure the color is the same color as the one we are moving.
                if (piece.PieceColor != board.WhoseMove)
                    continue;

                //For each valid move for this piece
                foreach (byte dst in piece.ValidMoves)
                {
                    Move move = new Move();
                    move.SrcPosition = x;
                    move.DstPosition = dst;

                    Piece pieceAttacked = board.Squares[move.DstPosition];

                    //If the move is a capture add it's value to the score
                    if (pieceAttacked != null)
                    {
                        move.Score += pieceAttacked.PieceValue;

                        if (piece.PieceValue < pieceAttacked.PieceValue)
                        {
                            move.Score += pieceAttacked.PieceValue - piece.PieceValue;
                        }
                    }

                    if (!piece.Moved)
                    {
                        move.Score += 10;
                    }

                    move.Score += piece.PieceActionValue;
                    positions.Add(move);
                }
            }
            return positions;
        }

        private static List<Move> GetCaptureMoves(Board board)
        {
            //We are going to store our result boards here           
            List<Move> positions = new List<Move>();
            for (byte x = 0; x < 64; x++)
            {
                Piece piece = board.Squares[x];

                //Make sure there is a piece on the square
                if (piece == null)
                    continue;

                //Make sure the color is the same color as the one we are moving.
                if (piece.PieceColor != board.WhoseMove)
                    continue;

                //For each valid move for this piece
                foreach (byte dst in piece.ValidMoves)
                {
                    //Only examing moves with attacks NOTE THIS IS WHERE EVALUATEMOVESQ differs from EVALUATEMOVES
                    if (board.Squares[dst] == null)
                    {
                        continue;
                    }

                    Move move = new Move();

                    move.SrcPosition = x;
                    move.DstPosition = dst;

                    Piece pieceAttacked = board.Squares[move.DstPosition];

                    move.Score += pieceAttacked.PieceValue;

                    if (piece.PieceValue < pieceAttacked.PieceValue)
                    {
                        move.Score += pieceAttacked.PieceValue - piece.PieceValue;
                    }

                    move.Score += piece.PieceActionValue;


                    positions.Add(move);
                }
            }
            return positions;
        }


        private static int SideToMoveScore(int score, ChessColor color)
        {
            if (color == ChessColor.Black)
                return -score;
            return score;
        }

        #endregion
    }
}
